package main

import (
	"strings"
)

type TrieNode struct {
	Children [26]*TrieNode
	Val string
}

func replaceWords3(dictionary []string, sentence string) string {
	root:=&TrieNode{}
	node:=root
	for _,word:=range dictionary {
		node=root
		for _,c:=range word {
			if node.Children[c-'a']==nil {
				node.Children[c-'a']=&TrieNode{}
			}
			node=node.Children[c-'a']
		}
		node.Val=word
	}
	res:=make([]byte, 0)
	i:=0
	node=root
	start:=0
	for i<len(sentence) {
		if sentence[i]==' ' {
			res=append(res, sentence[start:i]...)
			res=append(res, ' ')
			i++
			start=i
			node=root
			continue
		}
		if node.Children[sentence[i]-'a']==nil {
			for i<len(sentence) && sentence[i]!=' ' {
				i++
			}
			continue
		}
		node=node.Children[sentence[i]-'a']
		if len(node.Val)>0 {
			res=append(res, node.Val...)
			for i<len(sentence) && sentence[i]!=' ' {
				i++
			}
			if i<len(sentence) {
				res=append(res, ' ')
				i++
				start=i
				node=root
				continue
			} else {
				return string(res)
			}
		}
		i++
	}
	if start<i {
		res=append(res, sentence[start:i]...)
	}
	return string(res)
}

func replaceWords2(dictionary []string, sentence string) string {
	dictionarySet := map[string]bool{}
	for _, str := range dictionary {
		dictionarySet[str] = true
	}
	words := strings.Split(sentence, " ")
	for i, word := range words {
		for j := 1; j < len(word); j++ {
			if dictionarySet[word[:j]]{
				words[i] = word[:j]
				break
			}
		}
	}
	return strings.Join(words," ")
}

func replaceWords(dictionary []string, sentence string) string {
	dictionarySet := map[string]bool{}
	for _, s := range dictionary {
		dictionarySet[s] = true
	}
	words := strings.Split(sentence, " ")
	for i, word := range words {
		for j := 1; j <= len(word); j++ {
			if dictionarySet[word[:j]] {
				words[i] = word[:j]
				break
			}
		}
	}
	return strings.Join(words, " ")
}
